#include"stdafx.h"
#include "LinkedList.h"

template <typename T>
LinkedList<T>::LinkedList(){
	_size=0;
	_head=NULL;
}

template <typename T>
bool LinkedList<T>::isEmpty() const{
	return _size == 0; 
}

template <typename T>
int LinkedList<T>::getLength() const{
	return _size; 
}

template <typename T>
typename LinkedList<T>::ListNode* LinkedList<T>::find (int index) const {
	if ( (index<1)||(index>getLength()))
		return NULL;
	else {
		ListNode* cur = _head;
		for (int skip=1;skip<index;++skip)
			cur=cur->next;
		return cur;
	}
}

template <typename T>
void LinkedList<T>::retrieve(int userIdx, T& dataItem) const{
	if ((userIdx<1)||(userIdx>getLength()))
		throw string("Bad Index in retrieve");
	else { 
		ListNode *cur = find(userIdx);
		dataItem = cur->item;
	}
}

template <typename T>
void LinkedList<T>::insert(int userIdx,const T& newItem){
	int newLength = getLength() + 1;
	if ( (userIdx < 1) || (userIdx > newLength) )
		throw string("Bad Index in insert");
	else {
		ListNode *newPtr = new ListNode;
		newPtr->item = newItem;
		_size = newLength;
		if (userIdx == 1) {
			newPtr->next = _head;
			_head = newPtr;
		} else {
			ListNode *prev = find(userIdx-1);
			newPtr->next = prev->next;
			prev->next = newPtr;
		}
	}
}

template <typename T>
void LinkedList<T>::remove(int userIdx){
	ListNode *cur;
	if ( (userIdx < 1) || (userIdx > getLength()) )
		throw string("Bad index in remove");
	else {
		--_size;
		if (userIdx == 1) {
			cur = _head; // node to delete
			_head = _head->next;
		} 
		else {
			ListNode *prev = find(userIdx - 1);
			cur = prev->next; // node to delete
			prev->next = cur->next;
		} // end if
		cur->next = NULL;
		delete cur;
		cur = NULL;
	}
}

template <typename T>
void LinkedList<T>::clear(){
	while(!isEmpty()){
	remove(1);
	}
}